1574D - The Strongest Build - CodeForces Solution

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <cmath>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>

using namespace std;
using ll = long long;
#define endl '\n'


// First = hash, index 
// Second = final hash, final result
set<vector<int>> s; // Banned
int n;
const int MAX_LOW = -2e9;

pair<vector<int>, int> dp(vector<vector<int>> &v, vector<int> &hash, int i=0) {
	if (i == n) {
		if (s.find(hash) == s.end())
			return {{}, 0};
		
		else
			return {{}, MAX_LOW};
	}
	
	else {
		pair<vector<int>, int> result = {{}, MAX_LOW};
		
		for (int j = v[i].size()-1; j >= 0; j--) {
			hash.push_back(j+1);
			pair<vector<int>, int> nxtRes = dp(v, hash, i+1);
			
			nxtRes.first.push_back(j+1);
			nxtRes.second += v[i][j];
			
			if (nxtRes.second > result.second)
				result = nxtRes;
			
			if (s.find(hash) == s.end()) {
				hash.pop_back();
				break;
			}
			
			else
				hash.pop_back();
		}
		
		return result;
	}
}


vector<string> removeDupWord(string str)
{
	vector<string> result;
	string cur = "";
	
	for (char c : str) {
		if (c == ' ') {
			result.push_back(cur);
			cur = "";
		}
		
		else
			cur += c;
	}
	
	result.push_back(cur);
	return result;
}


void solve() 
{
	cin >> n;
	vector<vector<int>> v(n);
	
	for (int i = 0; i < n; i++) {
		int m;
		cin >> m;
		v[i] = vector<int>(m);
		
		for (int j = 0; j < m; j++)
			cin >> v[i][j];
	}
	
	int m;
	cin >> m;
	vector<vector<int>> banned(m, vector<int>(n));
	
	for (int i = 0; i < m; i++)
		for (int j = 0; j < n; j++)
			cin >> banned[i][j];
		
	for (int i = 0; i < m; i++) {
		vector<int> cur;
		
		for (int j = 0; j < n; j++) {
			cur.push_back(banned[i][j]);
			s.insert(cur);
		}
	}
	
	vector<int> hash;
	vector<int> res = dp(v, hash).first;
	reverse(res.begin(), res.end());
	
	for (int val : res)
		cout << val << " ";
	
	cout << endl;
}


int main() 
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	
//	int t;
//	cin >> t;
//	
//	while (t--)
//		solve();
	
	solve();
}